1. Field of the Invention
The present invention relates generally to data processing devices, and more particularly, to systems and methods for re-ordering data processed by multiple processing paths in data processing devices.
2. Description of Related Art
In network devices that must deliver high throughput in forwarding a stream of data, an existing approach is to provide n independent paths and distribute sub-streams of the data down each of the n paths. After processing by each of the n processing paths, the sub-streams are recombined to create an output stream. A problem that arises using this technique is that the different processing paths may have different delays. As a result, if a first data unit (e.g., a packet or cell) is sent down a first path at time t1 and a second data unit is sent down a second path at time t2>t1, the second data unit may nonetheless finish being processed before the first. Therefore, if nothing is done to correct for this differential delay, the recombined stream of data will be out-of-order relative to the input stream. Out-of-order data units can be problematic in a number of networking applications.
There are well-known algorithms for restoring order to mis-ordered streams at recombination time, based on attaching sequence numbers to consecutive data units at input, and sorting data units to restore consecutive sequence numbers on output. However, in some applications, a given output will not receive all sequence numbers from a given input, making the standard sorting algorithms impractical. It is also desirable for system performance to be able to re-order data units belonging to different streams separately.
Therefore, there exists a need for systems and methods that can preserve the order of data units in data streams that have been distributed across multiple paths in a data processing device, such as a network device.